/*
 * algoritmoConstr.cpp
 *
 *  Created on: Nov 11, 2012
 *      Author: ra083681
 */

#include "algoritmoConstr.h"

algoritmoConstr::algoritmoConstr() {
}

algoritmoConstr::~algoritmoConstr() {
}

double algoritmoConstr::construirSolucao(std::vector<ListGraph::Node> &current_solution) {

	// Contabiliza o numero de terminais passados
	unsigned l_iTerminalsPassed = 0;
	int ret;

	// Zera o custo total
	this->custo_total = 0;

	// Zera o vetor colorido
	for (int id = 0; id <= SteinerConstrainedPathSolver::graph.maxNodeId(); ++id) {
		colorido.push_back(false);
	}

	// Chama o metodo vizinhoMaisProximo ate que se passe por todos os terminais
	while (l_iTerminalsPassed < SteinerConstrainedPathSolver::num_terminals) {
		ret = this->vizinhoMaisProximo(current_solution, false);
		if (ret == -1) return -1;
		l_iTerminalsPassed += ret;
	}

	// Chama o metodo vizinhoMaisProximo ate chegar no destino
	while (ret = this->vizinhoMaisProximo(current_solution, true) != 1) {
		if (ret == -1) return -1;
	}

	// Retorna o custo da solucao gerada, que esta salva em current_solution
	return this->custo_total;
}

unsigned algoritmoConstr::vizinhoMaisProximo(std::vector<ListGraph::Node> &current_solution, bool ultimo_no) {

	ListGraph::Node noAtual;
	ListGraph::Node proximoNo;
	ListGraph::Node aux;

	ListGraph::Edge aresta;

	double dist_min = 0;
	bool ret = 0;
	int id;

	// Quando a solucao estiver vazia, procura um extremo para comecar.
	// Do contrario, pega o ultimo no da solucao para continuar.
	if (current_solution.size() == 0) {
		noAtual = this->encontraExtremo();
		current_solution.push_back(noAtual);
		cout << SteinerConstrainedPathSolver::graph.id(noAtual) << " ";
		colorido[SteinerConstrainedPathSolver::graph.id(noAtual)] = true;
		std::cout << SteinerConstrainedPathSolver::graph.id(noAtual) << " ";
	} else {
		noAtual = current_solution.back();
	}

	// Percorre todos os nos procurando arestas que liguem o ultimo no da solucao a outros nos;
	// A ordem de prioridade eh:
	// 		1) o no seguinte eh terminal
	// 		2) aresta de menor custo
	for (id = 0; id <= SteinerConstrainedPathSolver::graph.maxNodeId(); ++id) {
		if ((aresta = findEdge(SteinerConstrainedPathSolver::graph, noAtual, aux = SteinerConstrainedPathSolver::graph.nodeFromId(id))) != lemon::INVALID) {
			if (SteinerConstrainedPathSolver::terminal[aux] == true && colorido[id] == false) {
				if (SteinerConstrainedPathSolver::length[aresta] < dist_min || dist_min == 0 || ret == 0) {
					proximoNo = aux;
					dist_min = SteinerConstrainedPathSolver::length[aresta];
					ret = 1;
				}
			} else if (SteinerConstrainedPathSolver::extremos[aux] == true && colorido[id] == false) {
				if (ultimo_no == true) {
					current_solution.push_back(aux);
					this->custo_total += SteinerConstrainedPathSolver::length[aresta];
					return 1;
				}
			} else if (ret == 0 && colorido[id] == false) {
				if (SteinerConstrainedPathSolver::length[aresta] < dist_min || dist_min == 0) {
					proximoNo = aux;
					dist_min = SteinerConstrainedPathSolver::length[aresta];
				}
			}
		}
	}

	// Nao ha no para onde ir, retorna -1
	if (SteinerConstrainedPathSolver::graph.id(proximoNo) == SteinerConstrainedPathSolver::graph.id(noAtual)) return -1;

	// Coloca o no na solucao, atualiza o tempo e o vetor colorido
	current_solution.push_back(proximoNo);
	this->custo_total += dist_min;
	colorido[SteinerConstrainedPathSolver::graph.id(proximoNo)] = true;

	// O retorno é 0 caso passe por um no de steiner, e 1 do contrario
	return ret;
}

ListGraph::Node algoritmoConstr::encontraExtremo()
{
	ListGraph::Node ret;

	// Percorre os nos retornar o primeiro extremo que encontrar
	for (int id = 0; id <= SteinerConstrainedPathSolver::graph.maxNodeId(); ++id) {
		ret = SteinerConstrainedPathSolver::graph.nodeFromId(id);
		if (SteinerConstrainedPathSolver::extremos[ret] == true) {
			return ret;
		}
	}

	return ret;
}
